<!doctype html>
<html>
<head>
    <link rel="shortcut icon" href="../img/head.ico" type="image/x-icon">
    <link href="../css/bootstrap.min.css" rel="stylesheet" type="text/css">
    <link href="../css/bootstrap-responsive.min.css" rel="stylesheet" type="text/css">
    <script src="../js/jquery-3.2.1.min.js"></script>
    <script src="../js/bootstrap.min.js"></script>
    <meta charset="utf-8">
    <title>Diophantine equations</title>
</head>
<style>
    * {
        font-family: Baskerville, "Palatino Linotype", Palatino, "Century Schoolbook L", "Times New Roman", serif;
    }
    .v {
        font-size: 16px;
        width: 50px;
    }
</style>
<body style="text-align:center; font-size:24px;">
<p style="font-size:26px; margin: 20px;">Linear Diophantine Equations</p>

<form onSubmit="init(this); return false;" role="form" class="form-inline" method="post">
    <label for="a"></label>
    <input type="text" style="font-size: 16px;" class="v" name="a" id="a" placeholder="a"/>x&nbsp;+<label for="b"></label>
    <input type="text" style="font-size: 16px;" class="v" name="b" id="b" placeholder="b"/>y&nbsp;=<label for="c"></label>
    <input type="text" style="font-size: 16px;" class="v" name="c" id="c" placeholder="c"/>
    <br/>
    <input type="submit" class="btn btn-default" value=" Solve " style="font-size:24px; margin:10px;"/>
    <br/>
    <label style="font-size: 24px;" for="result">Result</label><br/>
    <textarea style="font-size: 18px; line-height: 24px; width: 400px;"  name="result" id="result" rows="15"></textarea>
    <br/><br/>
    By Hanzhi Zhou
</form>
<script>
    /**
     * @author Hanzhi Zhou
     * */
    /**
     * @type {int}
     * */
    var x = 0;
    /**
     * @type {int}
     * */
    var y = 1;
    /**
     * @type {int}
     * */
    var d = 0;
    function initVariables() {
        x = 0;
        y = 1;
        d = 0;
    }
    function init(form) {
        form.result.value = "";
        //initialize global variables
        initVariables();

        var a = parseInt(form.a.value);
        var b = parseInt(form.b.value);
        var c = parseInt(form.c.value);
        if (isNaN(a) || isNaN(b) || isNaN(c)) {
            form.result.value += "Illegal Input!!!";
            return;
        }
        form.result.value += a + 'x' + ' + ' + b + 'y' + ' = ' + c + '\n';
        gcd(a, b);
        form.result.value += 'gcd(' + a + ', ' + b + ')=' + d + '\n';

        // if gcd(a, b)|c
        if (Math.floor(c / d) === (c / d)) {
            a = a / d;
            b = b / d;
            c = c / d;
            // now gcd(a,b)=1
            form.result.value += a + 'x' + ' + ' + b + 'y' + ' = ' + c + '\n';
            initVariables();
            // find x, y such that ax+by=1
            gcd(a, b);
            form.result.value += a + '*' + x + ' + ' + b + '*' + y + ' = 1\n';
            form.result.value += 'A particular solution:\nx1=' + c * x + ', y1=' + c * y + '\n';
            form.result.value += 'General solutions:\n';
            form.result.value += 'x=' + c * x + '+' + b + '*n, y=' + c * y + '-' + a + '*n\n';
        }
        else {
            form.result.value += 'No solution!\nc is indivisible by gcd(a,b)!\n';

        }
        //form.result.value += y+'*'+a+' + '+x+'*'+b+' = '+d;
    }

    function gcd(a, b) {
        if (a === 0) {
            d = b;
        }
        else {
            var q = parseInt(b / a);
            var r = b % a;
            gcd(r, a);

            //working backward to obtain x and y such that ax+by=gcd(a, b)
            var temp = y;
            y = x;
            x = temp - parseInt(b / a) * x;
        }
    }
</script>
</body>
</html>
